package com.seven.leetcode.problems;

import java.util.Arrays;
import java.util.IntSummaryStatistics;

/**
 * 1723. 完成所有工作的最短时间
 * https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs/
 * 级别：Hard
 * <p>
 * 给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。
 * <p>
 * 请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。
 * 工人的工作时间是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案，使工人的最大工作时间得以最小化 。
 * 返回分配方案中尽可能最小的最大工作时间 。
 * <p>
 * 示例 1：
 * 输入：jobs = [3,2,3], k = 3
 * 输出：3
 * 解释：给每位工人分配一项工作，最大工作时间是 3 。
 * <p>
 * 示例 2：
 * 输入：jobs = [1,2,4,7,8], k = 2
 * 输出：11
 * 解释：按下述方式分配工作：
 * 1 号工人：1、2、8（工作时间 = 1 + 2 + 8 = 11）
 * 2 号工人：4、7（工作时间 = 4 + 7 = 11）
 * 最大工作时间是 11 。
 * <p>
 * 提示：
 * 1 <= k <= jobs.length <= 12
 * 1 <= jobs[i] <= 107
 *
 * @author : wenguang
 * @date : 2021/3/22 9:55
 */
public class FindMinimumTimeToFinishAllJobs {

    static int[] jobs;
    static int n, k;
    static int ans = Integer.MAX_VALUE;

    public static void main(String[] args) {
        int[] jobs = new int[]{1, 2, 4, 7, 8};
        int k = 2;
        System.out.println("in:\njobs: " + Arrays.toString(jobs) + "\nk: " + k);
        int res = minimumTimeRequired(jobs, k);
        System.out.println("out: " + res);
    }

    public static int minimumTimeRequired1(int[] jobs, int k) {
        int len = jobs.length;
        IntSummaryStatistics statistics = Arrays.stream(jobs)
            .summaryStatistics();
        if (k >= len) {
            return statistics.getMax();
        }

        int res = 0;
        int average = (int) Math.ceil((double) statistics.getSum() / k);

        if (statistics.getMax() >= average) {

        } else {

        }

        return res;
    }

    public static int minimumTimeRequired2(int[] jobs, int k) {
        Arrays.sort(jobs);
        int low = 0, high = jobs.length - 1;
        while (low < high) {
            int temp = jobs[low];
            jobs[low] = jobs[high];
            jobs[high] = temp;
            low++;
            high--;
        }

        int l = jobs[0], r = Arrays.stream(jobs).sum();
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(jobs, k, mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    public static boolean check(int[] jobs, int k, int limit) {
        int[] workloads = new int[k];
        return backtrack(jobs, workloads, 0, limit);
    }

    public static boolean backtrack(int[] jobs, int[] workloads, int i, int limit) {
        if (i >= jobs.length) {
            return true;
        }
        int cur = jobs[i];
        for (int j = 0; j < workloads.length; ++j) {
            if (workloads[j] + cur <= limit) {
                workloads[j] += cur;
                if (backtrack(jobs, workloads, i + 1, limit)) {
                    return true;
                }
                workloads[j] -= cur;
            }
            // 如果当前工人未被分配工作，那么下一个工人也必然未被分配工作
            // 或者当前工作恰能使该工人的工作量达到了上限
            // 这两种情况下我们无需尝试继续分配工作
            if (workloads[j] == 0 || workloads[j] + cur == limit) {
                break;
            }
        }

        return false;
    }

    public static int minimumTimeRequired(int[] _jobs, int _k) {
        jobs = _jobs;
        n = jobs.length;
        k = _k;

        IntSummaryStatistics statistics = Arrays.stream(jobs)
            .summaryStatistics();
        if (k >= n) {
            return statistics.getMax();
        }

        int average = (int) Math.ceil((double) statistics.getSum() / k);

        int[] sum = new int[k];
        dfs(0, 0, sum, average);
        return ans;
    }

    /**
     * 【补充说明】不理解可以看看下面的「我猜你问」的 Q5 哦 ~
     * <p>
     * u     : 当前处理到那个 job
     * used  : 当前分配给了多少个工人了
     * sum   : 工人的分配情况          例如：sum[0] = x 代表 0 号工人工作量为 x
     * max   : 当前的「最大工作时间」
     */
    static void dfs(int u, int used, int[] sum, int max) {
        if (max >= ans) {
            return;
        }

        if (u == n) {
            ans = max;
            return;
        }
        // 优先分配给「空闲工人」
        if (used < k) {
            sum[used] = jobs[u];
            dfs(u + 1, used + 1, sum, Math.max(sum[used], max));
            sum[used] = 0;
        }

        for (int i = 0; i < used; i++) {
            sum[i] += jobs[u];
            dfs(u + 1, used, sum, Math.max(sum[i], max));
            sum[i] -= jobs[u];
        }
    }
}
